class LRUCache {

    class DLinkNode {
        public int key;
        public int val;

        public DLinkNode prev;
        public DLinkNode next;

        public DLinkNode(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }

    public DLinkNode head;
    public DLinkNode tail;
    public Map<Integer,DLinkNode> map;
    public int n;

    public LRUCache(int capacity) {
        this.head = new DLinkNode(-1,-1);
        this.tail = new DLinkNode(-1,-1);
        head.next = tail;
        tail.prev = head;
        map = new HashMap<>();
        this.n = capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)) {
            DLinkNode node = map.get(key);
            refresh(node);
            return node.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        DLinkNode node = null;
        if(map.containsKey(key)) {
            //存在->覆盖
            node = map.get(key);
            node.val = value;
        } else {
            //还有空间否
            if(map.size() == n) {
                DLinkNode del = tail.prev;
                map.remove(del.key);
                delete(del);
            }
            //放入map
            node = new DLinkNode(key,value);
            map.put(key,node);
        }
        refresh(node);
    }

    //放到链表头部(删除+放置)
    public void refresh(DLinkNode node) {
        delete(node);
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        //这个步骤4一定得在1的后面
        head.next = node;

    }

    public void delete(DLinkNode node) {
        if(node.prev != null ) {
            DLinkNode pre = node.prev;
            pre.next = node.next;
            node.next.prev = pre;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */